package com.li.algorithm.leetcode.hot100;

import java.util.HashMap;

public class Test25 {

    public boolean hasCycle(ListNode head) {
        ListNode p = head;
        HashMap<ListNode, Integer> map = new HashMap<>();

        while (p != null) {
            if (map.get(p) != null) {
                return true;
            }
            map.put(p, 1);
            p = p.next;
        }
        return false;
    }


    /**
     * 快慢指针：如果快指针追上了慢指针，就说明有环
     */
    public boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != null && fast != null && fast.next != null) {
            if (fast == slow) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }


    public static void main(String[] args) {
        int[] arr = {3, 2, 0, -4};
        ListNode head = new ListNode(arr[0]);
        ListNode cycle = null;
        ListNode pre = head;
        for (int i = 1; i < arr.length; i++) {
            ListNode node = new ListNode(arr[i]);
            if (i == 1) {
                cycle = node;
            }
            pre.next = node;
            pre = node;
        }
        pre.next = cycle;
        Test25 test25 = new Test25();
        System.out.println(test25.hasCycle2(head));
    }
}
